//给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 
//
// 例如，从根到叶子节点路径 1->2->3 代表数字 123。 
//
// 计算从根到叶子节点生成的所有数字之和。 
//
// 说明: 叶子节点是指没有子节点的节点。 
//
// 示例 1: 
//
// 输入: [1,2,3]
//    1
//   / \
//  2   3
//输出: 25
//解释:
//从根到叶子节点路径 1->2 代表数字 12.
//从根到叶子节点路径 1->3 代表数字 13.
//因此，数字总和 = 12 + 13 = 25. 
//
// 示例 2: 
//
// 输入: [4,9,0,5,1]
//    4
//   / \
//  9   0
// / \
//5   1
//输出: 1026
//解释:
//从根到叶子节点路径 4->9->5 代表数字 495.
//从根到叶子节点路径 4->9->1 代表数字 491.
//从根到叶子节点路径 4->0 代表数字 40.
//因此，数字总和 = 495 + 491 + 40 = 1026. 
// Related Topics 树 深度优先搜索 
// 👍 303 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * Java：求根到叶子节点数字之和
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P129_SumRootToLeafNumbers {
    public static void main(String[] args) {
        Solution solution = new P129_SumRootToLeafNumbers().new Solution();
        // TODO 此处开始你的表演
        TreeNode treeNode = MyUtil.createTreeNode(1, 2, 3);
        MyUtil.print(solution.sumNumbers(treeNode));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 最优解
     */
    class Solution {
        public int sumNumbers(TreeNode root) {
            return traverse(root, 0);
        }

        private int traverse(TreeNode root, int sum) {
            if (root == null) {
                return 0;
            }
            sum = sum * 10 + root.val;
            if (root.left == null && root.right == null) {
                return sum;
            }
            return traverse(root.left, sum) + traverse(root.right, sum);
        }
    }
//    class Solution {
//        int sum = 0;
//        public int sumNumbers(TreeNode root) {
//            traverse(root, new ArrayList<>());
//            return sum;
//        }
//
//        private void traverse(TreeNode root, List<Integer> nums) {
//            if (root == null) {
//                return;
//            }
//            nums.add(root.val);
//            if (root.left == null && root.right == null) {
//                // 到叶子节点了，组合数字
//                StringBuilder sb = new StringBuilder("");
//                nums.forEach(num -> sb.append(num.toString()));
//                sum += Integer.parseInt(sb.toString());
//                nums.remove(nums.size() - 1);
//                return;
//            }
//
//            traverse(root.left, nums);
//            traverse(root.right, nums);
//            // 当前深度遍历完删除当前值，继续上层遍历
//            nums.remove(nums.size() - 1);
//        }
//    }
    //leetcode submit region end(Prohibit modification and deletion)

}